LeetCode Solutions

Appearance

42. 接雨水 ​

为保证权益，题目请参考 42. 接雨水(From LeetCode).

解决方案1 ​

CPP ​

C++
//
// Created by Keven Ge on 2020/4/4.
//  接雨水

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

class Solution {
public:
    int trap(vector<int> &height) {
        if(height.empty()){
            return 0;
        }

        // find the heightest the height.
        int max_height = INT_MIN;
        int max_index = INT_MAX;
        for (int i = 0; i < height.size(); ++i) {
            if (max_height < height[i]) {
                max_height = height[i];
                max_index = i;
            }
        }

        int ans = 0;

        // from the left
        int current_height = 0;
        for (unsigned i = 0; i < max_index; ++i) {
            if (height[i] > current_height) {
                ans -= current_height;
                ans += (height[i] - current_height) * (max_index - i - 1);
                current_height = height[i];
            } else {
                ans -= height[i];
            }
        }

        // from the right
        current_height = 0;
        for (unsigned i = height.size() - 1; i > max_index; --i) {
            if (height[i] > current_height) {
                ans -= current_height;
                ans += (height[i] - current_height) * (i - 1 - max_index);
                current_height = height[i];
            } else {
                ans -= height[i];
            }
        }

        return ans;
    }
};

int main() {
    vector<int> vec;
    vec.push_back(0);
    vec.push_back(1);
    vec.push_back(0);
    vec.push_back(2);
    vec.push_back(1);
    vec.push_back(0);
    vec.push_back(1);
    vec.push_back(3);
    vec.push_back(2);
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(1);

    Solution so;
    cout << so.trap(vec) << endl;
    return 0;
}

Python ​

python
# 42. 接雨水
# https://leetcode-cn.com/problems/trapping-rain-water/

################################################################################
# from typing import List


# class Solution:
#     def trap(self, height: List[int]) -> int:
#         """单调栈法"""
#         ans = 0
#         stacks = []
#         for i in range(len(height)):

#             while len(stacks) >= 2 and height[i] > stacks[-1][0]:
#                 t = stacks.pop()
#                 wid = i - stacks[-1][1] - 1
#                 hei = min(stacks[-1][0], height[i]) - t[0]
#                 ans += wid * hei

#             if len(stacks) == 1 and height[i] > stacks[-1][0]:
#                 stacks.pop()
#             stacks.append((height[i], i))

#         return ans


################################################################################
# from typing import List


# class Solution:
#     def trap(self, height: List[int]) -> int:
#         """双指针法"""

#         ans = 0

#         left = 0
#         right = len(height) - 1

#         maxLeft = 0
#         maxRight = 0

#         while left < right:
#             if height[left] <= height[right]:
#                 if height[left] < maxLeft:
#                     ans += min(maxLeft, height[right]) - height[left]
#                 maxLeft = max(maxLeft, height[left])
#                 left += 1
#             else:
#                 if height[right] < maxRight:
#                     ans += min(maxRight, height[left]) - height[right]
#                 maxRight = max(maxRight, height[right])
#                 right -= 1

#         return ans


################################################################################

from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        """双向"""
        maxHeight = -1
        maxIndex = -1
        for i, h in enumerate(height):
            if h > maxHeight:
                maxHeight = h
                maxIndex = i

        ans = 0

        # from left
        curHeight = 0

        for i in range(0, maxIndex):

            if height[i] < curHeight:
                ans -= height[i]

            else:
                ans -= curHeight

                wid = maxIndex - i - 1
                hei = height[i] - curHeight
                ans += wid * hei

                curHeight = height[i]

        # from right
        curHeight = 0

        for i in range(len(height) - 1, maxIndex, -1):

            if height[i] < curHeight:
                ans -= height[i]
            else:
                ans -= curHeight
                wid = i - maxIndex - 1
                hei = height[i] - curHeight
                ans += wid * hei
                curHeight = height[i]

        return ans


################################################################################


if __name__ == "__main__":
    solution = Solution()
    print(solution.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
    # print(solution.trap([4, 2, 0, 3, 2, 5]))